package com.ting.test.algorithms.查找算法.归并查找;

/**
 * 在一个数组中，
 * 对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数
 * 比如：[3,1,7,0,2]
 * 3的后面有：1，0
 * 1的后面有：0
 * 7的后面有：0，2
 * 0的后面没有
 * 2的后面没有
 * 所以总共有5个
 */
public class 逆序问题2 {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 1, 0, 5, 2, 1, 2, 4};
        int result = func(arr);
        System.out.println(result);
    }

    private static int func(int[] arr) {
        if (arr == null || arr.length == 1) {
            return 0;
        }

        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return process(arr, L, M) + process(arr, M + 1, R) + merge(arr, L, M, R);
    }

    private static int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int LIndex = L;
        int RIndex = M + 1;
        int index = 0;

        int count = 0;
        while (LIndex <= M && RIndex <= R) {
            if (arr[LIndex] > arr[RIndex] * 2) {
                count += R - RIndex + 1;
            }
            help[index++] = arr[LIndex] > arr[RIndex] ? arr[LIndex++] : arr[RIndex++];
        }
        while (LIndex <= M) {
            help[index++] = arr[LIndex++];
        }
        while (RIndex <= R) {
            help[index++] = arr[RIndex++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }

        return count;

    }
}
